package com.bupt.leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class ArrayProblem {
	/**
	 * leetCode 右移整形数组K次 rotate array question 189
	 * link:https://oj.leetcode.com/problems/rotate-array/
	 * 
	 */
	public void rotate1(int[] nums, int k) {
		k %= nums.length;
		k = nums.length - 1 - k;
		if (nums.length <= 1 || k < 0) {
			return;
		}
		reverse(nums, 0, k);
		reverse(nums, k + 1, nums.length - 1);
		reverse(nums, 0, nums.length - 1);
		
	}

	/**
	 * 反转数组
	 * 
	 * @param arr
	 * @param start
	 * @param end
	 */
	public void reverse(int[] arr, int start, int end) {
		int temp;
		for (int i = start; i <= (start + end) / 2; i++) {
			temp = arr[i];
			arr[i] = arr[start + end - i];
			arr[start + end - i] = temp;
		}
	}

	/**
	 * leetCode 右移整形数组K次 rotate array question 189 link:
	 * https://oj.leetcode.com/problems/rotate-array/
	 */
	public void rotate2(int[] nums, int k) {
		int temp;
		k %= nums.length;
		if (nums.length <= 1) {
			return;
		}
		while (k > 0) {
			temp = nums[nums.length - 1];
			for (int j = nums.length - 1; j > 0; j--) {
				nums[j] = nums[j - 1];
			}
			nums[0] = temp;
			k--;
		}
	}

	/**
	 * leetcode word search 题号： 79 url :
	 * https://leetcode.com/problems/word-search/
	 * 
	 * @param board
	 * @param word
	 * @return
	 */
	public boolean exist(char[][] board, String word) {
		if (word == null || word.length() == 0)
			return true;
		if (board == null || board.length == 0 || board[0].length == 0)
			return false;
		boolean[][] used = new boolean[board.length][board[0].length];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if (search(board, used, i, j, 0, word)) {
					return true;
				}
			}
		}
		return false;
	}
	/**
	 * 搜索递归体
	 * @param board
	 * @param used
	 * @param i
	 * @param j
	 * @param index
	 * @param word
	 * @return
	 */
	public boolean search(char[][] board, boolean[][] used, int i, int j,
			int index, String word) {
		if (index == word.length())
			return true;
		if (i < 0 || j < 0 || i >= board.length || j >= board[i].length
				|| used[i][j]|| word.charAt(index) != board[i][j])
			return false;
		used[i][j] = true;
		boolean res = search(board, used, i + 1, j, index + 1, word)
				|| search(board, used, i, j + 1, index + 1, word)
				|| search(board, used, i - 1, j, index + 1, word)
				|| search(board, used, i, j - 1, index + 1, word);
		used[i][j] = false;
		return res;
	}
	

}
